package Sort;

/**
 * @author chetaifu
 */
public class BasicQuickSort {
    private BasicQuickSort(){}

    public static void sort(Comparable[] arr){
        sort(arr, 0, arr.length -1);
    }

    private static void sort(Comparable[] arr, int low, int high){
        if(low >= high){
            return;
        }

        int p = partition(arr, low, high);
        sort(arr, low, p - 1);
        sort(arr, p + 1, high);
    }

    /** 对arr[l...r]部分进行partition操作
      * 返回p, 使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p] */
    private static int partition(Comparable[] arr, int low, int high){
        Comparable v = arr[low];
        int j = low;
        for (int i = low + 1; i <= high; i++) {
            if (arr[i].compareTo(v) < 0) {
                j ++;
                swap(arr, i, j);
            }
        }
        swap(arr, low, j);
        return j;
    }

    private static void swap(Object[] arr, int i, int j){
        Object tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}
